import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

public class HeapSort {

    // 使用大根堆进行排序
    public int[] heapSortMax(int[] arr) {
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

        // 将数组中的所有元素添加到优先级队列中
        for (int num : arr) {
            maxHeap.add(num);
        }

        // 从优先级队列中按顺序取出元素，存入数组中
        int[] res = new int[arr.length];
        int i = 0;
        while (!maxHeap.isEmpty()) {
            Integer poll = maxHeap.poll();
            res[i] = poll;
            i++;
        }
        return res;
    }

    // 使用小根堆进行排序
    public int[] heapSortMin(int[] arr) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // 将数组中的所有元素添加到优先级队列中
        for (int num : arr) {
            minHeap.add(num);
        }

        // 从优先级队列中按顺序取出元素，存入数组中
        int[] res = new int[arr.length];
        int i = 0;
        while (!minHeap.isEmpty()) {
            Integer poll = minHeap.poll();
            res[i] = poll;
            i++;
        }
        return res;
    }

    public static void main(String[] args) {
        HeapSort heapSort = new HeapSort();

        int[] arrMax = {3, 2, 1, 5, 6, 4};
        int[] res1 = heapSort.heapSortMax(arrMax);
        System.out.println("大根堆排序结果（从小到大）: " + Arrays.toString(res1));

        int[] arrMin = {3, 2, 1, 5, 6, 4};
        int[] res2 = heapSort.heapSortMin(arrMin);
        System.out.println("小根堆排序结果（从大到小）: " +Arrays.toString(res2) );
    }
}
